#ifndef __SIMPLE_LK_LIST_WITHOUT_first_NODE_H__
#define __SIMPLE_LK_LIST_WITHOUT_first_NODE_H__

#include "./node.h"
template <class ElemType>
class SimpleLinkListWithoutHeadNode
{
protected:
    Node<ElemType> *first;                          // 指向首元素节点的指针
    Node<ElemType> *GetElemPtr(int position) const; // 返回指向第position个元素的指针
public:
    SimpleLinkListWithoutHeadNode();
    // 无参构造函数
    virtual ~SimpleLinkListWithoutHeadNode();
    // 析构函数
    int Length() const;
    // 求表长度
    bool Empty() const;
    // 判断表是否为空
    void Clear();
    // 清空线性表
    void Traverse(void (*visit)(const ElemType &)) const;
    // 遍历线性表
    bool GetElem(int position, ElemType &e) const;
    // 求指定位置得元素值
    ElemType GetElem(int position) const;
    // 返回指定位置元素值
    bool SetElem(int position, const ElemType &e) const;
    // 设置指定位置的元素值
    bool Delete(int position, ElemType &e);
    // 删除元素
    bool Delete(int position);
    // 删除元素
    bool Insert(int position, const ElemType &e);
    // 插入元素
    SimpleLinkListWithoutHeadNode(const SimpleLinkListWithoutHeadNode<ElemType> &source);
    // 复制构造函数
    SimpleLinkListWithoutHeadNode<ElemType> &operator=(const SimpleLinkListWithoutHeadNode<ElemType> &source);
    // 重载赋值运算符
};

template <class ElemType>
SimpleLinkListWithoutHeadNode<ElemType>::SimpleLinkListWithoutHeadNode()
// 构造空链表
{
    first = NULL;
}

template <class ElemType>
SimpleLinkListWithoutHeadNode<ElemType>::~SimpleLinkListWithoutHeadNode()
// 清空链表
{
    Clear();
}

template <class ElemType>
int SimpleLinkListWithoutHeadNode<ElemType>::Length() const
// 返回链表长度
{
    int num = 0;
    for (Node<ElemType> *curptr = first; curptr != NULL; num++, curptr = curptr->next)
        ;
    return num;
}

template <class ElemType>
bool SimpleLinkListWithoutHeadNode<ElemType>::Delete(int position, ElemType &e)
// 删除第position个元素并用e返回其值
{
    if (position < 1 || position > Length())
    {
        std::cout<<position;
        return false; // 范围错误
}
    Node<ElemType> *tmp;
    if (position > 1)
    { // 如果不是第一个节点
        tmp = GetElemPtr(position - 1);
        Node<ElemType> *nex = tmp->next;
        tmp->next = nex->next;
        e = nex->data;
        delete nex;
        return true;
    }
    tmp = first;
    e = first->data;
    first = first->next;
    delete tmp;
    return true;
}

template <class ElemType>
bool SimpleLinkListWithoutHeadNode<ElemType>::Delete(int position)
// 删除第position个元素
{
    if (position < 1 || position > Length())
        return false; // 范围错误

    Node<ElemType> *tmp;
    if (position > 1)
    { // 如果不是第一个节点
        tmp = GetElemPtr(position - 1);
        Node<ElemType> *nex = tmp->next;
        tmp->next = nex->next;
        delete nex;
    }
    tmp = first;
    first = first->next;
    delete tmp;
    return true;
}

template <class ElemType>
void SimpleLinkListWithoutHeadNode<ElemType>::Clear()
// 清空链表
{
    while (Length() > 0)
    {
        Delete(1);
    }
}

template <class ElemType>
Node<ElemType> *SimpleLinkListWithoutHeadNode<ElemType>::GetElemPtr(int position) const
// 获得指向指定位置节点的指针
{
    if (position < 1 || position > Length())
        return NULL; // 范围错误
    int curposition = 1;
    Node<ElemType> *curptr = first;
    while (curposition < position)
    {
        curposition++;
        curptr = curptr->next;
    }
    return curptr;
}

template <class ElemType>
bool SimpleLinkListWithoutHeadNode<ElemType>::Empty() const
// 判断链表是否为空
{
    return first == NULL;
}

template <class ElemType>
void SimpleLinkListWithoutHeadNode<ElemType>::Traverse(void (*visit)(const ElemType &)) const
// 遍历线性表
{
    for (Node<ElemType> *curptr = first; curptr != NULL; curptr = curptr->next)
    {
        (*visit)(curptr->data);
    }
}

template <class ElemType>
bool SimpleLinkListWithoutHeadNode<ElemType>::GetElem(int position, ElemType &e) const
// 获得指定位置元素的值并用e返回
{
    Node<ElemType> *tmp = GetElemPtr(position);
    if (tmp == NULL)
        return false;
    e = tmp->data;
    return true;
}

template <class ElemType>
ElemType SimpleLinkListWithoutHeadNode<ElemType>::GetElem(int position) const
// 获得指定位置元素的值
{
    if (position < 1 || position > Length())
        return ElemType(0); // 范围错误
    int curposition = 1;
    Node<ElemType> *curptr = first;
    while (curposition < position)
    {
        curposition++;
        curptr = curptr->next;
    }
    return curptr->data;
}

template <class ElemType>
bool SimpleLinkListWithoutHeadNode<ElemType>::SetElem(int position, const ElemType &e) const
// 设置指定位置元素的值
{
    Node<ElemType> *tmp = GetElemPtr(position);
    if (tmp == NULL)
        return false;
    tmp->data = e;
    return true;
}

template <class ElemType>
bool SimpleLinkListWithoutHeadNode<ElemType>::Insert(int position, const ElemType &e)
// 在第position个元素前插入元素
{
    if (position < 1 || position > Length() + 1) // 范围错
        return false;
    Node<ElemType> *newptr;
    if (position > 1)
    {
        Node<ElemType> *tmp = GetElemPtr(position - 1);
        newptr = new Node<ElemType>(e, tmp->next);
        tmp->next = newptr;
        return true;
    }
    newptr = new Node<ElemType>(e, first);
    first = newptr;
    return true;
}

template <class ElemType>
SimpleLinkListWithoutHeadNode<ElemType>::SimpleLinkListWithoutHeadNode(const SimpleLinkListWithoutHeadNode<ElemType> &source)
// 复制构造函数
{
    ElemType e;
    first = NULL;
    int length = source.Length();
    for (int curposition = 1; curposition <= length; curposition++)
    {
        e = source.GetElem(curposition);
        Insert(curposition, e);
    }
}

template <class ElemType>
SimpleLinkListWithoutHeadNode<ElemType> &SimpleLinkListWithoutHeadNode<ElemType>::operator=(const SimpleLinkListWithoutHeadNode<ElemType> &source)
// 重载赋值运算
{
    if (&source != this)
    {
        int length = source.Length();
        ElemType e;
        Clear();
        for (int curposition = 1; curposition <= length; curposition++)
        {
            e = source.GetElem(curposition);
            Insert(curposition, e);
        }
    }
    return *this;
}

#endif